#include <iostream>
#include <algorithm>
#include <string>
#include <cstdio>
#include <vector>
using namespace std;
class Solution
{
public:
    vector<vector<string>> ans;
    vector<string> slice;
    vector<vector<bool>> record;
    string putAt(int index, int n)
    {
        if (index < 0 || index >= n)
            return {};
        string ret(n, '.');
        ret[index] = 'Q';
        return ret;
    }
    void getSlice(vector<vector<bool>> &record, vector<string> &slice)
    {
        slice.clear();
        int n = record.size();
        for (auto &line : record)
        {
            for (int i = 0; i < n; ++i)
            {
                if (line[i] == true)
                {
                    slice.push_back(putAt(i, n));
                    break;
                }
            }
        }
        return;
    }
    void init(int n)
    {
        slice.resize(n);
        record.resize(n);
        for (auto &line : record)
        {
            line.resize(n);
        };
    }
    bool check(int i, int j, vector<vector<bool>> &record)
    {
        int n = record.size();
        //对第i行进行check
        for (int j = 0; j < n; ++j)
        {
            if (record[i][j] == true)
                return false;
        }
        //对第j列进行check
        for (int i = 0; i < n; ++i)
        {
            if (record[i][j] == true)
                return false;
        }
        //对对角线进行check i+j = k
        for (int x = 0, y = i + j; x < n; ++x)
        {
            y = i + j - x;
            if (!(y >= 0 && y < n))
                continue;
            if (record[x][y] == true)
                return false;
        }
        //对副对角线进行check i-j = k x-y = k ,y = x - k
        for (int x = 0, y = x - (i - j); x < n; ++x)
        {
            y = x - (i - j);
            if (!(y >= 0 && y < n))
                continue;
            if (record[x][y] == true)
                return false;
        }
        return true;
    }
    void dfs(int cur, int n) //当前处于第cur行
    {
        if (cur >= n)
        {
            getSlice(record, slice);
            ans.push_back(slice);
            return;
        }
        for (int j = 0; j < n; ++j)
        {
            if (check(cur, j, record) == true)
            {
                record[cur][j] = true;
                dfs(cur + 1, n);
                record[cur][j] = false;
            }
        }
    }
    vector<vector<string>> solveNQueens(int n)
    {
        init(n);
        dfs(0, n);
        return ans;
    }
};